package com.LeeCode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 两棵二叉搜索树中的所有元素
 */

public class Code1305 {
    public static void main(String[] args) {

    }

    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        List<Integer> ans = new LinkedList<>();
        TreeNode node1 = root1, node2 = root2;
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();
        while (node1 != null || node2 != null || !stack1.isEmpty() || !stack2.isEmpty()) {
            while (node1 != null) {
                stack1.push(node1);
                node1 = node1.left;
            }
            while (node2 != null) {
                stack2.push(node2);
                node2 = node2.left;
            }

            if (!stack1.isEmpty()) node1 = stack1.peek();
            if (!stack2.isEmpty()) node2 = stack2.peek();
            if (node2 == null || node1 != null && node1.val <= node2.val) {
                ans.add(node1.val);
                stack1.pop();
                node1 = node1.right;
                node2 = null;
            } else {
                ans.add(node2.val);
                stack2.pop();
                node2 = node2.right;
                node1 = null;
            }
        }
        return ans;
    }
}
